package study.datastructure.link;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-09-20 20:34
 */

import java.util.Map;
import java.util.function.Consumer;

/**
 2024/9/20,
 */
//环形双向链表
public class DoublyLinkListSentinel {
    //首尾
      static Node sentinel=new Node(null,-1,null);
      

    public DoublyLinkListSentinel() {
        sentinel.prev=sentinel;
        sentinel.next=sentinel;
    }

    /**
     * 向头部添加元素
     */
    public  void addFirst(int value) {
        Node a=sentinel;
        Node b=sentinel.next;

        Node inserted=new Node(a,value,b);
        b.prev=inserted;
        a.next=inserted;
    }

    /**
     * 遍历链表
     */
    public  void loop(Consumer<Integer> consumer){
        Node pointer=sentinel.next;
        while (pointer!=sentinel) {
            consumer.accept(pointer.value);
            pointer=pointer.next;
        }
    }

    public void removeLast(){
        Node removed=sentinel.prev;
        Node a=sentinel;
        if (removed==sentinel){
            illegalIndex(-1);
        }
        Node b=removed.prev;
        b.next=a;
        a.prev=b;
        System.gc();
    }
    public void removeByValue(int value){
        Node removed=findByValue(value);
        if (removed==sentinel){
            return;
        }
        Node a=removed.prev;
        Node b=removed.next;
        a.next=b;
        b.prev=a;

    }

    private Node findByValue(int value) {
        Node p=sentinel.next;
        while (p!=sentinel){
            if (p.value==value) {
                return p;
            }
            p=p.next;
        }
        return sentinel;
    }


    /**
     * 节点内部类
     */
     public  static class Node{ //内部类 节点
         int value;
         Node next=null;
         Node prev=null;

        public Node(Node prev,int value,Node next) {
            this.prev=prev;
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 添加最后节点
     */
    //特色功能
    public void addLast(Integer value) {
        Node prev=sentinel.prev;
        Node inserted=new Node(prev,value,sentinel);

        prev.next=inserted;
        sentinel.prev=inserted;
    }


    /**
     * 找到最后一个节点
     * @return
     */

    private Node findLastNode() {
        Node p; //尾节点的判断细节
        for (p=sentinel;p.next!=null;p=p.next){
        }

        return p;
    }

    public Integer findNodeValueByIndex(Integer index){
        Node indexNode=findNode(index);
        if (indexNode==null){
            illegalIndex(index);
        }
        return indexNode.value;

    }

    private Node findNode(Integer index) {
        Node p;
        int i=-1;//索引
        for(p=sentinel;p!=sentinel;p=p.next,i++){
            if (index==i){
                return p;
            }
        }
        return null;
    }


    public void insert(int index, int value) {
        //超过索引范围
        Node previousNode = findNode(index - 1);
        if (previousNode==null){
                illegalIndex(index);
                return;
        }
        Node next=previousNode.next;
        Node inserted=new Node(previousNode,value,next);
        previousNode.next=inserted;
        next.prev=inserted;
    }



    public void remove(int index){
        Node previousNode = findNode(index-1);
        if (previousNode==null){
            illegalIndex(index);
            return;
        }
        Node removed=previousNode.next;
        if (removed==null){
            illegalIndex(index);
            return;
        }
        previousNode.next=removed.next;

    }


    private static void illegalIndex(int index) {
        throw new IllegalArgumentException(String
                .format("参数index [%d],不合法%n", index));
    }


}
